//你需要用一个包括括号和整数的字符串构建一棵二叉树。 
//
// 输入的字符串代表一棵二叉树。它包括整数和随后的 0 、1 或 2 对括号。整数代表根的值，一对括号内表示同样结构的子树。 
//
// 若存在子结点，则从左子结点开始构建。 
//
// 
//
// 示例 1: 
// 
// 
//输入： s = "4(2(3)(1))(6(5))"
//输出： [4,2,6,3,1,5]
// 
//
// 示例 2: 
//
// 
//输入： s = "4(2(3)(1))(6(5)(7))"
//输出： [4,2,6,3,1,5,7]
// 
//
// 示例 3: 
//
// 
//输入： s = "-4(2(3)(1))(6(5)(7))"
//输出： [-4,2,6,3,1,5,7]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 10⁴ 
// 输入字符串中只包含 '(', ')', '-' 和 '0' ~ '9' 
// 空树由 "" 而非"()"表示。 
// 
//
// Related Topics 树 深度优先搜索 字符串 二叉树 👍 101 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func str2tree(s string) *TreeNode {
if 0 == len(s) {
return nil
}
stack := []*TreeNode{}
for i := 0; i < len(s); i++ {
if s[i] == ')' {
stack = stack[:len(stack)-1]
} else if (s[i] >= '0' && s[i] <= '9') || s[i] == '-' {
j := i
for i+1 < len(s) && s[i+1] >= '0' && s[i+1] <= '9' {
i++
}
val, _ := strconv.Atoi(s[j : i+1])
node := &TreeNode{Val: val}
if len(stack) != 0 {
parent := stack[len(stack)-1]
if parent.Left == nil {
parent.Left = node
} else {
parent.Right = node
}
}
stack = append(stack, node)
}
}
return stack[0]
}

//leetcode submit region end(Prohibit modification and deletion)
